﻿//1.回文子串
//https://leetcode.cn/problems/palindromic-substrings/description/
//给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
//回文字符串 是正着读和倒过来读一样的字符串。
//子字符串 是字符串中的由连续字符组成的一个序列。
//示例 1：
//输入：s = "abc"
//输出：3
//解释：三个回文子串 : "a", "b", "c"
//示例 2：
//输入：s = "aaa"
//输出：6
//解释：6个回文子串 : "a", "a", "a", "aa", "aa", "aaa"
//提示：
//1 <= s.length <= 1000
//s 由小写英文字母组成

//解法：
//dp[i][j]表示：以i位置元素开始，j位置元素结束能否构成回文子串
//如果s[i] != s[j] 则d[i][j] = false
//如果s[i] == s[j] 
//(1)i == j dp[i][j] = true; 
//(2)i + 1 == j dp[i][j] = true; 
//(2)i + 1 < j 则d[i][j] = dp[i + 1][j - 1];
class Solution {
public:
    int countSubstrings(string s)
    {
        int n = s.size();
        int sum = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));
        //从字符串末尾开始向前遍历,从右下角开始，按行从下到上，每行从左到右
        for (int i = n - 1; i >= 0; i--)
        {
            //j从i开始向后遍历（只考虑i<=j的情况）
            for (int j = i; j < n; j++)
            {
                //首尾字符相等时进行判断
                if (s[i] == s[j])
                {
                    //1. 单个字符：i == j，肯定是回文
                    //2. 相邻字符：j == i+1，首尾相等就是回文  
                    //3. 长度>2：取决于去掉首尾后的子串是否是回文
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                // 如果当前子串是回文，计数增加
                if (dp[i][j]) sum++;
            }
        }
        return sum;
    }
};



//2.最长回文子串
//https://leetcode.cn/problems/longest-palindromic-substring/description/
//给你一个字符串 s，找到 s 中最长的 回文 子串。
//示例 1：
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//示例 2：
//输入：s = "cbbd"
//输出："bb"
//提示：
//1 <= s.length <= 1000
//s 仅由数字和英文字母组成

//解法：与上题一致
//在dp[i][j]为true的前提下判断j - i + 1的值是否大于len即可，大于的话更新len和begin

class Solution {
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int begin = 0, len = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j])
                    if (j - i + 1 > len) len = j - i + 1, begin = i;
            }
        }
        return s.substr(begin, len);
    }
};



//3.分割回文串IV
//https://leetcode.cn/problems/palindrome-partitioning-iv/description/
//给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
//当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
//示例 1：
//输入：s = "abcbdd"
//输出：true
//解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
//示例 2：
//输入：s = "bcbddxy"
//输出：false
//解释：s 没办法被分割成 3 个回文子字符串。
//提示：
//3 <= s.length <= 2000
//s​​​​​​ 只包含小写英文字母。


//解法：
//dp[i][j]表示：以i位置元素开始，j位置元素结束能否构成回文子串
//找两个分割点i和j(i <= j),将s字符串分成三段[0,i - 1],[i,j],[j + 1,n - 1]
//利用dp表判断这三段是否为true，都为true的话返回 true 
class Solution {
public:
    bool checkPartitioning(string s)
    {
        int n = s.size();
        //预处理回文信息：首先，我们使用动态规划来预处理所有可能的子串是否为回文。
        //创建一个二维数组dp，其中dp[i][j]表示子串s[i..j]是否为回文。
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
            }
        }
        //寻找分割点：在预处理完成后，我们尝试所有可能的分割点。
        //具体来说，我们寻找两个分割点i和j，将字符串分成三部分：[0, i - 1]、[i, j] 和[j + 1, n - 1]。
        //如果这三部分都是回文，则返回true。
        for (int i = 1; i < n - 1; i++)
        {
            for (int j = i; j < n - 1; j++)
            {
                //检查三部分是否都是回文
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true;
            }
        }
        return false;
    }
};


//4.分割回文穿II
//https://leetcode.cn/problems/palindrome-partitioning-ii/
//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
//返回符合要求的 最少分割次数 。
//示例 1：
//输入：s = "aab"
//输出：1
//解释：只需一次分割就可将 s 分割成["aa", "b"] 这样两个回文子串。
//示例 2：
//输入：s = "a"
//输出：0
//示例 3：
//输入：s = "ab"
//输出：1
//提示：
//1 <= s.length <= 2000
//s 仅由小写英文字母组成

//解法：
//ispalindrome[i][j]表示：以i位置元素开始，j位置元素结束能否构成回文子串
//dp[i]表示：将区间[0,i]字符串分割成回文子串的最小次数
//如果s[0..i]本身就是回文,不需要分割dp[i] = 0
//否则遍历所有可能的分割点j(0 < j <= i)，
//如果s[j..i]是回文，那么可以在j处切一刀
//前面部分s[0..j - 1]的最小分割次数是dp[j - 1]，加上当前这一刀就是dp[i]
//即dp[i] = dp[j - 1] + 1
//在0 < j <= i的所有分割点j中找到最小的dp[j - 1]即可
//dp[i] = min(dp[j - 1],dp[i])
class Solution {
public:
    int minCut(string s)
    {
        int n = s.size();
        vector<vector<bool>> ispalindrome(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j]) ispalindrome[i][j] = i + 1 < j ? ispalindrome[i + 1][j - 1] : true;
            }
        }
        vector<int> dp(n, INT_MAX);
        for (int i = 0; i < n; i++)
        {
            if (ispalindrome[0][i]) dp[i] = 0;
            else
            {
                for (int j = 1; j <= i; j++)
                    // 前提条件如果s[j..i]是回文
                    if (ispalindrome[j][i])
                        //在位置j处切一刀，前面部分s[0..j - 1]的最小分割次数是dp[j - 1]，加上当前这一刀
                        dp[i] = min(dp[i], dp[j - 1] + 1);
            }
        }
        return dp[n - 1];
    }
};




//5.最长回文子序列
//https://leetcode.cn/problems/longest-palindromic-subsequence/description/
//给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
//子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
//示例 1：
//输入：s = "bbbab"
//输出：4
//解释：一个可能的最长回文子序列为 "bbbb" 。
//示例 2：
//输入：s = "cbbd"
//输出：2
//解释：一个可能的最长回文子序列为 "bb" 。
//提示：
//1 <= s.length <= 1000
//s 仅由小写英文字母组成



//解法：
//dp[i][j]表示：以i位置元素开始j位置元素结束的所有子序列中，最长回文子序列的长度
//如果s[i] == s[j],这两个字符可以构成回文的一部分dp[i][j] = dp[i+1][j-1] + 2
//如果s[i] != s[j],取去掉首字符或去掉尾字符的较大值dp[i][j] = max(dp[i+1][j], dp[i][j-1])
class Solution {
public:
    int longestPalindromeSubseq(string s)
    {
        int n = s.size();
        //dp[i][j]表示：以i位置元素开始j位置元素结束的所有子序列中，最长回文子序列的长度
        vector<vector<int>> dp(n, vector<int>(n));
        //从右下角开始填充dp表，确保计算dp[i][j]时，dp[i+1][j-1]等子问题已经计算过
        for (int i = n - 1; i >= 0; i--)
        {
            //单个字符本身就是长度为1的回文
            dp[i][i] = 1;
            //从i+1开始，因为j必须大于i
            for (int j = i + 1; j < n; j++)
            {
                //首尾字符相同，可以构成回文
                //长度 = 内部子串的最长回文长度 + 2（首尾两个字符）
                if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    //首尾字符不同，取两种情况的较大值：
                    //1. 去掉首字符：dp[i+1][j]
                    //2. 去掉尾字符：dp[i][j-1]
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        //返回整个字符串的最长回文子序列长度
        return dp[0][n - 1];
    }
};


//6.让字符串成为回文串的最少插入次数
//https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/
//给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
//请你返回让 s 成为回文串的 最少操作次数 。
//「回文串」是正读和反读都相同的字符串。
//示例 1：
//输入：s = "zzazz"
//输出：0
//解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
//示例 2：
//输入：s = "mbadm"
//输出：2
//解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
//示例 3：
//输入：s = "leetcode"
//输出：5
//解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
//提示：
//1 <= s.length <= 500
//s 中所有字符都是小写字母。

//解法：
//dp[i][j]表示：s区间[i,j]中，让字符串成为回文串的最少插入次数
//如果s[i] == s[j],当i == j 或 i + 1 == j时插入次数为0，
//当i + 1 < j时，两端的字符相同，那么它们已经匹配，不需要额外插入考虑[i + 1,j - 1]区间
//即在区间[i,j]的插入次数等于在区间[i + 1,j - 1]的插入次数
//dp[i][j] = dp[i + 1][j - 1]
//如果s[i] != s[j],两端的字符不同，我们需要在某一端插入字符
//在右端插入s[i],dp[i][j - 1] + 1
//在左端插入s[j],dp[i + 1][j] + 1
//取两者中的较小值：dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1


class Solution {
public:
    int minInsertions(string s)
    {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        //从下往上，从左往右填充dp表
        //这种填充顺序确保在计算dp[i][j]时，dp[i+1][j-1]、dp[i][j-1]、dp[i+1][j]都已经计算完成
        for (int i = n - 1; i >= 0; i--)
            for (int j = i + 1; j < n; j++)
                //两端字符相同，直接使用内部子串的结果
                //其中i == j和i + 1 == j的情况初始化已经完成 
                if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
                //两端字符不同，选择在左端或右端插入字符的较小代价
                else dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1;
        return dp[0][n - 1];
    }
};